def maxDominoScore(xs:Array[Column],col:Int):Int= {
    var maxEndingHere:Array[Int]=new Array[Int](col)
    maxEndingHere(0)=Math.abs(xs(0).up-xs(0).down) //->1
    maxEndingHere(1)=Math.max(maxEndingHere(0)+vertDiff(xs,1),
                              horizDiff(xs,1))
    for(i <- 2 to col-1) {
        val first= maxEndingHere(i-1) + vertDiff(xs,i)
        val second=maxEndingHere(i-2) + horizDiff(xs,i)
        maxEndingHere(i)=Math.max(first,second)
    }
    maxEndingHere(col-1)
}

test("this is the highest domino score") {
    val xs:Array[Column]= Array[Column](new Column(8,9),new Column(6,7),new Column(2,1),new Column(3,2))
    maxDominoScore(xs,4) should equal (12)    
}     
class Column(u:Int,d:Int) {
    var up=u
    var down=d
}

def vertDiff(xs:Array[Column],i:Int)= {
    Math.abs((xs(i).up-xs(i).down))
}
def horizDiff(xs:Array[Column],i:Int)= {
    Math.abs(xs(i-1).up-xs(i).up)+Math.abs(xs(i-1).down-xs(i).down)
}

def maxDominoScore2(xs:Array[Column],col:Int):(Int,List[String])= {
    var positions=new Array[List[String]](col)
    var maxEndingHere:Array[Int]=new Array[Int](col)
    
    maxEndingHere(0)=vertDiff(xs,0)
    positions(0)=List("V")
    
    var a=maxEndingHere(0)+vertDiff(xs,1)
    var b=horizDiff(xs,1)
    if(a>b){
        maxEndingHere(1)=a
        positions(1)=positions(0):::List("V")
    }
    else {
        maxEndingHere(1)=b
        positions(1)=List("HL","HR")
    }
    
    for(i <- 2 to col-1) {
        val first= maxEndingHere(i-1) + vertDiff(xs,i)
        val second=maxEndingHere(i-2) + horizDiff(xs,i)
        if(first>second) {
            maxEndingHere(i)=first
            positions(i)=positions(i-1):::List("V")
        }
        else {
            maxEndingHere(i)=second
            positions(i)=positions(i-2):::List("HL","HR")
        }
    }
    (maxEndingHere(col-1),positions(col-1))
}

    
test("positions") {
    val ys:Array[Column]= Array[Column](new Column(8,9),new Column(6,7),new Column(2,1),new Column(3,2))
    val result=maxDominoScore2(ys,4) 
    result._1 should equal (12)
    result._2 should equal (List("V","HL","HR","V"))    
}